#ifndef __BINARYTREE_H_
#define __BINARYTREE_H_
#include<iostream>
template<typename T>
class BinaryTree
{
public:
    BinaryTree();
    ~BinaryTree();
    void Insert(const T&element);
    T* FindElement(const T&element);
    void Remove(const T& element);
    template<typename U>
    friend std::ostream& operator<<(std::ostream&os,const BinaryTree<U>& tree);
   

private:
    struct   TreeNode
    {
        TreeNode(const T&element):date(element)
        {
            Left=right=parent=nullptr;
        }
         T date;//数据域
        TreeNode *Left;//左孩子
        TreeNode *right;//右孩子
        TreeNode *parent;//双亲节点
    };
    TreeNode * InsertNode(TreeNode*node,const T&element);
    void FreeNode(TreeNode* node);
    T* FindNode(TreeNode*node,const T& element);
    void PrevTravel(TreeNode*node);
    void MidTravel(TreeNode*node);
    void PostvTravel(TreeNode*node);
    TreeNode *  RemoveNode(TreeNode*node,const T& element);
    //获取一棵树中的最小值点
    TreeNode *GetMinNode(TreeNode*node);

    //右旋
    TreeNode *RotateRight(TreeNode *node);
    //左旋
    TreeNode *RotateLeft(TreeNode *node);
    //左右旋
    TreeNode *RotateLeftRight(TreeNode*node);
    //右左旋
    TreeNode *RotateRightLeft(TreeNode*node);
    
    int GetNodeHeight(TreeNode *node);
    //左右子树高度差
    int LRDeviation(TreeNode* node);
    TreeNode *root;
};
template<typename T>
std::ostream& operator<<(std::ostream&os,const BinaryTree<T>& tree)
{
    std::cout<<"前：";
    PrevTravel(tree.root);
    std::cout<<std::endl;
     std::cout<<"中：";
     MidTravel(tree.root);
    std::cout<<std::endl;
     std::cout<<"后：";
    PostvTravel(tree.root);
    std::cout<<std::endl;
    return os;
}
template<typename T>
BinaryTree<T>::BinaryTree()
{
    root=nullptr;
}
template<typename T>
BinaryTree<T>::~BinaryTree()
{
    FreeNode(root);
}
template<typename T>
void BinaryTree<T>::Insert(const T &element)
{
    root=InsertNode(root,element);
}
template<typename T>
T *BinaryTree<T>::FindElement(const T &element)
{
   return FindNode(root,element);
}
template<typename T>
void BinaryTree<T>::Remove(const T &element)
{
    root=RemoveNode(root,element);
}


template<typename T>
typename BinaryTree<T>::TreeNode* BinaryTree<T>::InsertNode(TreeNode *node, const T &element)
{
    if(node==nullptr)//如果为空构建
    {
        return new TreeNode(element);
    }
    if(node->date==element)//数据已经存在
    {
        return node;
    }
    else if(node->date>element)
    {
          node->Left=InsertNode(node->Left,element);
          //左边重失衡
          if(LRDeviation(node)>1)
          {
            //左左失衡
            if(cmpBig(node->Left->date,element))
            {
                //右旋
                node=RotateRight(node);
            }
            //左右失衡
            else
            {
                //左右旋
                node=RotateLeftRight(node);
            }
          }
    }
    else{
        node->right=InsertNode(node->right,element);
        //右边重失衡
        if(LRDeviation(node)<-1)
        {
            //右右失衡
            if(element>node->right->date)
            {
                node=RotateLeft(node);
            }
            else
            {
                node=RotateRightLeft(node);
            }
        }
    }
    return node;   
}
template<typename T>
void BinaryTree<T>::FreeNode(TreeNode *node)
{
    if(node==nullptr)
        return;
    FreeNode(node->Left);
    FreeNode(node->right);
    delete node;

}
template<typename T>
 T *BinaryTree<T>::FindNode(TreeNode *node, const T & element)
{
    if(node==nullptr)
        return nullptr;
    if(node->date==element)
        return &node->date;
    if(node->date<element)
        return FindNode(node->right,element);
    if( node->date>element)
        return FindNode(node->Left,element);
    return nullptr;
}
template<typename T>
typename BinaryTree<T>::TreeNode *BinaryTree<T>::RemoveNode(TreeNode *node, const T &element)
{
   if(node ==nullptr)
        return nullptr;
    if(cmpBig(element, node->date))
    {
        node->right=RemoveNode(node->right,element);
    }
    else if(cmpBig(node->date,element))
    {
        node->Left=RemoveNode(node->Left,element);
    }
    else
    {
       //叶子
       if(node->Left==nullptr&&node->right==nullptr)
       {
           delete node;
           return nullptr;   
       }
       //左右孩子都存在
       else if(node->Left!=nullptr&&node->right!=nullptr)
       {
        //取右子树中最小节点
            TreeNode *min=GetMinNode(node->right);
        //将最小节点的值赋给node
            node->date=min->date;
        //删掉最小节点
            node->right=RemoveNode(node->right,min->date);
        
       }
       //只有一个孩子
       else
       {
            TreeNode *childNode=node->Left?node->Left:node->right;
            delete node;
            node= childNode;
       }
    }
     if(LRDeviation(node)>1)
          {
            //左左失衡
            if(LRDeviation(node->Left)>0)//左边高度比右边高
            {
                //右旋
                node=RotateRight(node);
            }
            //左右失衡
            else
            {
                //左右旋
                node=RotateLeftRight(node);
            }
          }
     if(LRDeviation(node)<-1)
        {
            //右右失衡
            if(LRDeviation(node->right)<0)//右边高度比左边高
            {
                node=RotateLeft(node);
            }
            else
            {
                node=RotateRightLeft(node);
            }
        }

  
    //同一判断返回node
    return node;
}
template<typename T>
typename BinaryTree<T>:: TreeNode *BinaryTree<T>::GetMinNode(TreeNode*node)
{
    TreeNode *MinNode=node;
    while(node->Left!=nullptr)
        MinNode=MinNode->Left;
    return MinNode;
}
template<typename T>
typename BinaryTree<T>:: TreeNode *BinaryTree<T>::RotateRight(TreeNode *node)
{
    TreeNode *t=node->Left;
    node->Left=t->right;
    t->right=node;
    return t;
}
template<typename T>
typename BinaryTree<T>:: TreeNode *BinaryTree<T>::RotateLeft(TreeNode *node)
{
    TreeNode *t=node->right;
    node->right=t->Left;
    t->Left=node;
    return t;
}
template<typename T>
typename BinaryTree<T>:: TreeNode *BinaryTree<T>::RotateLeftRight(TreeNode *node)
{
    //左子树左旋
    node->Left=RotateLeft(node->Left);
    //整棵树右旋
    return  RotateRight(node);
}
template<typename T>
typename BinaryTree<T>:: TreeNode *BinaryTree<T>::RotateRightLeft(TreeNode *node)
{
  //右子树右旋
  node->right=RotateRight(node->right);
  //整棵树左旋
  return RotateLeft(node);
}
template<typename T>
int BinaryTree<T>::GetNodeHeight(TreeNode *node)
{
    if(node==nullptr)
        return 0;
    int leftHeight=GetNodeHeight(node->Left);
    int RightHeight=GetNodeHeight(node->right);
    return (leftHeight>RightHeight?leftHeight:RightHeight)+1;
    
}
template<typename T>
int BinaryTree<T>::LRDeviation(TreeNode *node)
{
    if(node==nullptr)
        return 0;
    return GetNodeHeight(node->Left)-GetNodeHeight(node->right);
}
template<typename T>
void BinaryTree<T>::PrevTravel(TreeNode *node)
{
    if(node==nullptr)
        return;
    std::cout<<node->data<<" ";
    PrevTravel(node->Left);
    PrevTravel(node->right);
}
template<typename T>
void BinaryTree<T>::MidTravel(TreeNode *node)
{
    if(node==nullptr)
        return;
    MidTravel(node->Left);
    print(node->date);
    MidTravel(node->right);
}
template<typename T>
void BinaryTree<T>::PostvTravel(TreeNode *node)
{
    if(node==nullptr)
        return;
    PostvTravel(node->Left);
    PostvTravel(node->right);
    print(node->date);
}

#endif